package com.cn.codebrush.leetcode.editor.cn;
// 2022-10-13 17:32:24
// 5  最长回文子串
//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 5805 👎 0


public class LongestPalindromicSubstring{

public static void main(String[] args) {

Solution solution = new LongestPalindromicSubstring().new Solution();
    System.out.println(solution.longestPalindrome("aabcb"));
}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = s.substring(0,1);
        boolean[][] dp = new boolean[n][n];

        /*如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，
        来判断了[i,j]是不是回文，那结果一定是不对的。
            所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。
            有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j - 1]都是经过计算的。*/

        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                //j-i<2  保证每一个都是计算过的
                if(s.charAt(i) == s.charAt(j) && (j-i<2 || dp[i+1][j-1])){
                    dp[i][j] = true;
                    res = s.substring(i,j+1).length()>res.length()?s.substring(i,j+1):res;
                }
            }

        }

        return res;
    }






















}
//leetcode submit region end(Prohibit modification and deletion)


}